package problem46_Permutations;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
	private final List<List<Integer>> result=new LinkedList<>();
	public List<List<Integer>> permute(int[] nums) {
		Integer[] nums2=new Integer[nums.length];
		for(int i=0;i<nums.length;i++)
			nums2[i]=nums[i];
		dfs(nums2,0,nums2.length);
		return result;
	}

	private void dfs(Integer[] nums,int start,int end){
		if(start==end)
			result.add(new LinkedList<>(Arrays.asList(nums)));
		for(int i=start;i<end;i++){
			swap(start,i,nums);
			dfs(nums,start+1,end);
			swap(start,i,nums);
		}
			
	}
	
	private void swap(int i,int j,Integer[] nums){
		int tmp=nums[i];
		nums[i]=nums[j];
		nums[j]=tmp;
	}
	
	public static void main(String[] args){
		System.out.println(new Solution().permute(new int[]{1,2,3}));
	}
}
